When a computer application provides data to a device for printing and/or display, an intermediate description of the page is often given to device driver software in a page description language, which provides descriptions of graphic objects to be rendered onto the page or display. This contrasts some arrangements where raster image data is generated directly and transmitted for printing or display. Examples of page description languages include PostScript and PCL. Equivalently, a set of descriptions of graphic objects may be provided in function calls to a graphics interface, such as the Microsoft Windows GDI, or Unix's X-11. The page image is typically rendered for printing and/or display by an object-based graphics system, or a raster image processor (RIP).
Most object-based graphics systems utilize a large volume of memory, known in the art as a frame store or a page buffer. Such a frame store or page buffer is used to hold a pixel-based image data representation of the page or screen for subsequent printing and/or display. Typically, the outlines of the graphic objects are calculated, filled with color values and written into the frame store. For two-dimensional graphics, objects that appear in front of other objects are simply written into the frame store after the background objects, thereby replacing the background on a pixel by pixel basis. This is commonly known in the art as “Painter's algorithm”. In the Painter's algorithm objects are considered in priority order, from the rearmost object to the foremost object, and typically, each object is rasterized in scanline order and pixels are written to the frame store in sequential runs along each scanline. Some graphics interfaces allow a logical or arithmetic operation to be specified and performed between one or more graphics objects and the already rendered pixels in the frame buffer. In these cases the rendering principle remains the same: objects (or groups of objects) are rasterized in scanline order, and the result of the specified operation is calculated and written to the frame store in sequential runs along each scanline. There are essentially two problems with this technique.
The first problem with the above technique is that the technique requires fast random access to all of the pixels in the frame store. This is because each new object may affect any pixel in the frame store. For this reason, the frame store is normally kept in semiconductor random access memory (RAM). For high-resolution color printers the amount of RAM required is very large, typically in excess of 100 Mbytes, which is costly and difficult to run at high speed. The second problem with the above technique is that many pixels which have been previously painted (i.e., rendered) are subsequently over-painted (i.e., re-rendered) by later objects. Such over-painting of pixels with earlier objects is inefficient.
One method for overcoming the large frame-store problem discussed above is the use of “banding”. When banding is used, only part of a frame store exists in memory at any one time. All objects to be drawn are retained in a “display list”, which is an internal representation of the information required to draw the objects on a page. The display list is considered in object order as above, and only those pixel operations which fall within the fraction of the page which is held in the band are actually performed. After all objects in the display list have been drawn, the band is sent to the printer (or to intermediate storage) and the process is repeated for the next band of the page. There are some penalties with the banding technique, however. For example, the objects being drawn must be reconsidered many times, once for each band. As the number of bands increases, so does the repetitious examination of the objects requiring rendering. Also, the technique of banding does not solve the problem of over-painting.
Some other graphic systems consider an image in scan line order. Again, all objects on a page are retained in a display list. On each scanline, objects which intersect that scanline are then considered in priority order. For each object in priority order, spans of pixels between intersection points of the object edges with the scanline are filled in a line store. This scan line order technique overcomes the large frame store problem. However, the scan line order technique still suffers from the over-painting problem.
Other graphic systems utilise pixel-sequential rendering to overcome both the large frame store problem and the over-painting problem. In these systems, each pixel is generated in raster order. Again, all objects to be drawn are retained in a display list. On each scan line, the edges of objects, which intersect that scanline, are held in increasing order of their intersection with the scan line. These points of intersection, or edge crossings, are considered in turn, and used to toggle an array of fields. The array of fields indicate the activity of the objects in the display list. There is one activity field for each object painting operation that is of interest on a scan line. There is also a field to indicate operations that do not require previously generated data. Between each pair of edges considered, the color data for each pixel, which lies between a first of the edges and a second of the edges, is generated using a priority encoder. The priority encoder is used on the activity flags to determine which operations are required to generate the color, and performing only those operations for the span of pixels between the two edges. In preparation for the next scanline, the coordinate of intersection of each edge is updated in accordance with the nature of each edge, and the edges are sorted into increasing order of intersection with that scanline. Any new edges are also merged into the list of edges.
Graphic systems which use pixel-sequential rendering have significant advantages over other graphics systems in that there is no frame store or line store and no unnecessary over-painting. Further, object priorities are dealt with in constant order time by a priority encoder, rather than in order N time, where N is the number of priorities. In most such pixel-sequential rendering graphic systems every point on a page to be rendered is represented by an X coordinate (hereinafter referred to as an ‘X-value’) and a corresponding Y coordinate (hereinafter referred to as a ‘Y-value’) in integer fixed-point format (e.g. 28.4 integer fixed-point format). A monotonic curve representing the outline of a graphic object, for example, is described on such systems as a series of coordinate points in integer fixed-point format. The current Y-value for a particular point is greater than or equal to a next Y-value assuming an increasing scanline position (Y) in the Y direction.
The disadvantages with using integer fixed point format arithmetic in pixel-sequential rendering graphic systems will now be described in detail. However, before proceeding, a brief review of terminology used throughout the following specification will be discussed:                A.B: represents a fixed point number (e.g. 28.4) which itself is used to represent a rational number. The fixed point number ranges from −(2A+B−1−1) to +(2A+B−1), where A and B are positive integers, and A equals the number of bits required to represent an integer part of the rational number and B equals the number of bits required to represent a fractional part of the rational number. For example, if P is an A.B fixed point number is used to represent the rational number Q, thenQ=P/2B  (1)         Letting P=8, A=28 and B=4 (i.e., a 28.4 fixed point number), then the rational number Q is determined as follows:Q=8/24= 8/16=½.        A%B: represents the remainder of an integer division A/B;        INT (a): represents the integer part of a real number ‘a’;        INT(a/b): represents the integer division result of integer ‘a’ divided by integer ‘b’; and        a/b: represents the real number division of a number ‘a’ divided by a number ‘b’.        
As will be described in more detail below, an edge of an object starts at an integer scanline position (Y). The X-value and Y-value of the starting point of the edge are then typically examined as to the priority (i.e., z-order value) of the objects corresponding to the edge to determine whether particular objects contribute pixels to a particular scan line.
For pixel generation, the calculation of an integer pixel position X-value for an edge is typically performed for each integer scanline position (Y) incrementally in a Y direction of the edge (i.e. from the start point of the edge to the end point of the edge). If the current scanline position (Y) is greater than the Y-value for the end-point of the edge, then the edge is no longer valid and is considered as not being active for that scanline. The integer pixel position (X) for an edge is determined from a corresponding ‘real’ X-value corresponding to the point that the current scanline crosses the edge (i.e., the edge crossing X-value). The real X-value of an edge crossing point is rounded based on a specific ‘rounding rule’ associated with the crossed edge to determine an integer edge crossing X-value for the real X-value.
There are three main types of edge crossing X-value rounding rules as follows, where the real X-value is represented as a rational number a/b, ‘a’ represents the integer nominator and ‘b’ represents the nonzero integer denominator:                (i) Flooring Rule: the integer edge crossing X-value of an edge at a current scanline position (Y) (i.e., corresponding to a pixel position (X) on that scanline) is the flooring value of the real (i.e., rational) edge crossing X-value at the current scanline position value (Y). The Flooring Rule for the rational number a/b is: FLOOR(a/b)=INT(a/b), b>0;        (ii) Ceiling Rule: the integer edge crossing X-value of an edge at a current scanline position (Y) (i.e., corresponding to a pixel position (X) on that scanline) is the ceiling value of the real (i.e., rational) edge crossing X-value at the current scanline position value (Y). The Ceiling Rule for the rational number a/b is: CEIL(a/b)=INT ((a+b−1)/b), b>0; and        (iii) Rounding Rule: the integer edge crossing X-value of the edge at a current scanline position (Y) (i.e., corresponding to a pixel position (X) on that scanline) is the rounding value of the real (i.e, rational) edge crossing X-value at the current scanline position (Y). The Rounding Rule for a rational number a/b is: ROUND(a/b)=INT((2a+b)/2b), b>0.        
The Flooring, Ceiling and Rounding Rules for an A.B fixed point number x are defined, respectively, as:FLOOR(x)=INT(x/2B)  (2)CEIL(x)=INT((x+2B−1)/2B)  (3)ROUND(x)=INT((x+2B−1)/2B)  (4)
For edges associated with each of the above rounding rules, the first edge crossing X-value is determined at the intersection of an edge segment with a corresponding horizontal line at the Y-value corresponding to the current scanline position (Y). The corresponding Y-value is equal to the floor value of the Y-value representing the start point of the edge segment. The last edge crossing Y-value is equal to the floor value of the corresponding end point Y-value of the edge segment less one. One disadvantage with using the integer fixed point format is that if the result of any fixed-point format arithmetic operation is outside a particular range (i.e., dependent on the number of bits used to represent the result value), then the result value is overflowed. The fractional part of such a result value also has a maximum range depending on the number of bits used to represent the fractional part of the result value. Therefore, the fractional part of the result value must be approximated to a real number with a corresponding error value.
The error value resulting from such integer fixed-point arithmetic can accumulate in any graphic system that processes a high number of fractional parts (e.g. a system using 18.14 integer fixed-point format arithmetic) to determine edge crossing values. Clipping is required in such a system for all points, since the graphic system has only eighteen bits to represent the integer part of a result when input points are normally in 28.4 integer fixed-point format which has twenty-eight bits to represent an integer value.
A further problem with a graphic system using 18.14 integer fixed-point format arithmetic, for example, to determine edge crossing values, is that such a system cannot accurately represent near vertical, near horizontal or long line segments. Such line segments must be broken down into smaller segments and subsequently connected together. Again, the error value resulting from the corresponding increase in integer fixed-point arithmetic accumulates, sometimes resulting in gaps between adjoining boundary objects.
One known method for tracking scan line edge crossing points is based on the basic linear line equation (i.e., x=my+c where m & c are constants). In this known method, edge crossing calculations for a line segment (i.e., from a first point to a second point on an edge) are performed in an accumulated fashion. However, again, the error is linearly increasing as the scan line position (Y) increases. Due to the sensitive nature of the Rounding, Ceiling or Flooring Rules discussed above, a smallest fractional error in a real (i.e., rational) edge crossing X-value might erroneously increase or decrease the integer crossing X-value by one pixel.
Thus, a need clearly exists for an improved method of accurately representing monotonic curves on pixel-sequential rendering graphic systems.